home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Miscellaneous / Berkeley_db / btree / bt_split.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-04  |  21.6 KB  |  827 lines  |  [TEXT/????]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_split.c    8.1 (Berkeley) 6/4/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42.  
  43. #define    __DBINTERFACE_PRIVATE
  44. #include <limits.h>
  45. #include <stdio.h>
  46. #include <stdlib.h>
  47. #include <string.h>
  48.  
  49. #include <db.h>
  50. #include "btree.h"
  51.  
  52. static int     bt_broot __P((BTREE *, PAGE *, PAGE *, PAGE *));
  53. static PAGE    *bt_page
  54.             __P((BTREE *, PAGE *, PAGE **, PAGE **, u_int *, size_t));
  55. static int     bt_preserve __P((BTREE *, pgno_t));
  56. static PAGE    *bt_psplit
  57.             __P((BTREE *, PAGE *, PAGE *, PAGE *, u_int *, size_t));
  58. static PAGE    *bt_root
  59.             __P((BTREE *, PAGE *, PAGE **, PAGE **, u_int *, size_t));
  60. static int     bt_rroot __P((BTREE *, PAGE *, PAGE *, PAGE *));
  61. static recno_t     rec_total __P((PAGE *));
  62.  
  63. #ifdef STATISTICS
  64. u_long    bt_rootsplit, bt_split, bt_sortsplit, bt_pfxsaved;
  65. #endif
  66.  
  67. /*
  68.  * __BT_SPLIT -- Split the tree.
  69.  *
  70.  * Parameters:
  71.  *    t:    tree
  72.  *    sp:    page to split
  73.  *    key:    key to insert
  74.  *    data:    data to insert
  75.  *    flags:    BIGKEY/BIGDATA flags
  76.  *    ilen:    insert length
  77.  *    skip:    index to leave open
  78.  *
  79.  * Returns:
  80.  *    RET_ERROR, RET_SUCCESS
  81.  */
  82. int
  83. __bt_split(t, sp, key, data, flags, ilen, skip)
  84.     BTREE *t;
  85.     PAGE *sp;
  86.     const DBT *key, *data;
  87.     u_long flags;
  88.     size_t ilen;
  89.     u_int skip;
  90. {
  91.     BINTERNAL *bi;
  92.     BLEAF *bl, *tbl;
  93.     DBT a, b;
  94.     EPGNO *parent;
  95.     PAGE *h, *l, *r, *lchild, *rchild;
  96.     indx_t nxtindex;
  97.     size_t n, nbytes, nksize;
  98.     int parentsplit;
  99.     char *dest;
  100.  
  101.     /*
  102.      * Split the page into two pages, l and r.  The split routines return
  103.      * a pointer to the page into which the key should be inserted and with
  104.      * skip set to the offset which should be used.  Additionally, l and r
  105.      * are pinned.
  106.      */
  107.     h = sp->pgno == P_ROOT ?
  108.         bt_root(t, sp, &l, &r, &skip, ilen) :
  109.         bt_page(t, sp, &l, &r, &skip, ilen);
  110.     if (h == NULL)
  111.         return (RET_ERROR);
  112.  
  113.     /*
  114.      * Insert the new key/data pair into the leaf page.  (Key inserts
  115.      * always cause a leaf page to split first.)
  116.      */
  117.     h->linp[skip] = h->upper -= ilen;
  118.     dest = (char *)h + h->upper;
  119.     if (ISSET(t, R_RECNO))
  120.         WR_RLEAF(dest, data, flags)
  121.     else
  122.         WR_BLEAF(dest, key, data, flags)
  123.  
  124.     /* If the root page was split, make it look right. */
  125.     if (sp->pgno == P_ROOT &&
  126.         (ISSET(t, R_RECNO) ?
  127.         bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
  128.         goto err2;
  129.  
  130.     /*
  131.      * Now we walk the parent page stack -- a LIFO stack of the pages that
  132.      * were traversed when we searched for the page that split.  Each stack
  133.      * entry is a page number and a page index offset.  The offset is for
  134.      * the page traversed on the search.  We've just split a page, so we
  135.      * have to insert a new key into the parent page.
  136.      *
  137.      * If the insert into the parent page causes it to split, may have to
  138.      * continue splitting all the way up the tree.  We stop if the root
  139.      * splits or the page inserted into didn't have to split to hold the
  140.      * new key.  Some algorithms replace the key for the old page as well
  141.      * as the new page.  We don't, as there's no reason to believe that the
  142.      * first key on the old page is any better than the key we have, and,
  143.      * in the case of a key being placed at index 0 causing the split, the
  144.      * key is unavailable.
  145.      *
  146.      * There are a maximum of 5 pages pinned at any time.  We keep the left
  147.      * and right pages pinned while working on the parent.   The 5 are the
  148.      * two children, left parent and right parent (when the parent splits)
  149.      * and the root page or the overflow key page when calling bt_preserve.
  150.      * This code must make sure that all pins are released other than the
  151.      * root page or overflow page which is unlocked elsewhere.
  152.      */
  153.     while ((parent = BT_POP(t)) != NULL) {
  154.         lchild = l;
  155.         rchild = r;
  156.  
  157.         /* Get the parent page. */
  158.         if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
  159.             goto err2;
  160.  
  161.          /*
  162.          * The new key goes ONE AFTER the index, because the split
  163.          * was to the right.
  164.          */
  165.         skip = parent->index + 1;
  166.  
  167.         /*
  168.          * Calculate the space needed on the parent page.
  169.          *
  170.          * Prefix trees: space hack when inserting into BINTERNAL
  171.          * pages.  Retain only what's needed to distinguish between
  172.          * the new entry and the LAST entry on the page to its left.
  173.          * If the keys compare equal, retain the entire key.  Note,
  174.          * we don't touch overflow keys, and the entire key must be
  175.          * retained for the next-to-left most key on the leftmost
  176.          * page of each level, or the search will fail.  Applicable
  177.          * ONLY to internal pages that have leaf pages as children.
  178.          * Further reduction of the key between pairs of internal
  179.          * pages loses too much information.
  180.          */
  181.         switch (rchild->flags & P_TYPE) {
  182.         case P_BINTERNAL:
  183.             bi = GETBINTERNAL(rchild, 0);
  184.             nbytes = NBINTERNAL(bi->ksize);
  185.             break;
  186.         case P_BLEAF:
  187.             bl = GETBLEAF(rchild, 0);
  188.             nbytes = NBINTERNAL(bl->ksize);
  189.             if (t->bt_pfx && !(bl->flags & P_BIGKEY) &&
  190.                 (h->prevpg != P_INVALID || skip > 1)) {
  191.                 tbl = GETBLEAF(lchild, NEXTINDEX(lchild) - 1);
  192.                 a.size = tbl->ksize;
  193.                 a.data = tbl->bytes;
  194.                 b.size = bl->ksize;
  195.                 b.data = bl->bytes;
  196.                 nksize = t->bt_pfx(&a, &b);
  197.                 n = NBINTERNAL(nksize);
  198.                 if (n < nbytes) {
  199. #ifdef STATISTICS
  200.                     bt_pfxsaved += nbytes - n;
  201. #endif
  202.                     nbytes = n;
  203.                 } else
  204.                     nksize = 0;
  205.             } else
  206.                 nksize = 0;
  207.             break;
  208.         case P_RINTERNAL:
  209.         case P_RLEAF:
  210.             nbytes = NRINTERNAL;
  211.             break;
  212.         default:
  213.             abort();
  214.         }
  215.  
  216.         /* Split the parent page if necessary or shift the indices. */
  217.         if (h->upper - h->lower < nbytes + sizeof(indx_t)) {
  218.             sp = h;
  219.             h = h->pgno == P_ROOT ?
  220.                 bt_root(t, h, &l, &r, &skip, nbytes) :
  221.                 bt_page(t, h, &l, &r, &skip, nbytes);
  222.             if (h == NULL)
  223.                 goto err1;
  224.             parentsplit = 1;
  225.         } else {
  226.             if (skip < (nxtindex = NEXTINDEX(h)))
  227.                 memmove(h->linp + skip + 1, h->linp + skip,
  228.                     (nxtindex - skip) * sizeof(indx_t));
  229.             h->lower += sizeof(indx_t);
  230.             parentsplit = 0;
  231.         }
  232.  
  233.         /* Insert the key into the parent page. */
  234.         switch(rchild->flags & P_TYPE) {
  235.         case P_BINTERNAL:
  236.             h->linp[skip] = h->upper -= nbytes;
  237.             dest = (char *)h + h->linp[skip];
  238.             memmove(dest, bi, nbytes);
  239.             ((BINTERNAL *)dest)->pgno = rchild->pgno;
  240.             break;
  241.         case P_BLEAF:
  242.             h->linp[skip] = h->upper -= nbytes;
  243.             dest = (char *)h + h->linp[skip];
  244.             WR_BINTERNAL(dest, nksize ? nksize : bl->ksize,
  245.                 rchild->pgno, bl->flags & P_BIGKEY);
  246.             memmove(dest, bl->bytes, nksize ? nksize : bl->ksize);
  247.             if (bl->flags & P_BIGKEY &&
  248.                 bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR)
  249.                 goto err1;
  250.             break;
  251.         case P_RINTERNAL:
  252.             /*
  253.              * Update the left page count.  If split
  254.              * added at index 0, fix the correct page.
  255.              */
  256.             if (skip > 0)
  257.                 dest = (char *)h + h->linp[skip - 1];
  258.             else
  259.                 dest = (char *)l + l->linp[NEXTINDEX(l) - 1];
  260.             ((RINTERNAL *)dest)->nrecs = rec_total(lchild);
  261.             ((RINTERNAL *)dest)->pgno = lchild->pgno;
  262.  
  263.             /* Update the right page count. */
  264.             h->linp[skip] = h->upper -= nbytes;
  265.             dest = (char *)h + h->linp[skip];
  266.             ((RINTERNAL *)dest)->nrecs = rec_total(rchild);
  267.             ((RINTERNAL *)dest)->pgno = rchild->pgno;
  268.             break;
  269.         case P_RLEAF:
  270.             /*
  271.              * Update the left page count.  If split
  272.              * added at index 0, fix the correct page.
  273.              */
  274.             if (skip > 0)
  275.                 dest = (char *)h + h->linp[skip - 1];
  276.             else
  277.                 dest = (char *)l + l->linp[NEXTINDEX(l) - 1];
  278.             ((RINTERNAL *)dest)->nrecs = NEXTINDEX(lchild);
  279.             ((RINTERNAL *)dest)->pgno = lchild->pgno;
  280.  
  281.             /* Update the right page count. */
  282.             h->linp[skip] = h->upper -= nbytes;
  283.             dest = (char *)h + h->linp[skip];
  284.             ((RINTERNAL *)dest)->nrecs = NEXTINDEX(rchild);
  285.             ((RINTERNAL *)dest)->pgno = rchild->pgno;
  286.             break;
  287.         default:
  288.             abort();
  289.         }
  290.  
  291.         /* Unpin the held pages. */
  292.         if (!parentsplit) {
  293.             mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  294.             break;
  295.         }
  296.  
  297.         /* If the root page was split, make it look right. */
  298.         if (sp->pgno == P_ROOT &&
  299.             (ISSET(t, R_RECNO) ?
  300.             bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
  301.             goto err1;
  302.  
  303.         mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
  304.         mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
  305.     }
  306.  
  307.     /* Unpin the held pages. */
  308.     mpool_put(t->bt_mp, l, MPOOL_DIRTY);
  309.     mpool_put(t->bt_mp, r, MPOOL_DIRTY);
  310.  
  311.     /* Clear any pages left on the stack. */
  312.     return (RET_SUCCESS);
  313.  
  314.     /*
  315.      * If something fails in the above loop we were already walking back
  316.      * up the tree and the tree is now inconsistent.  Nothing much we can
  317.      * do about it but release any memory we're holding.
  318.      */
  319. err1:    mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
  320.     mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
  321.  
  322. err2:    mpool_put(t->bt_mp, l, 0);
  323.     mpool_put(t->bt_mp, r, 0);
  324.     __dbpanic(t->bt_dbp);
  325.     return (RET_ERROR);
  326. }
  327.  
  328. /*
  329.  * BT_PAGE -- Split a non-root page of a btree.
  330.  *
  331.  * Parameters:
  332.  *    t:    tree
  333.  *    h:    root page
  334.  *    lp:    pointer to left page pointer
  335.  *    rp:    pointer to right page pointer
  336.  *    skip:    pointer to index to leave open
  337.  *    ilen:    insert length
  338.  *
  339.  * Returns:
  340.  *    Pointer to page in which to insert or NULL on error.
  341.  */
  342. static PAGE *
  343. bt_page(t, h, lp, rp, skip, ilen)
  344.     BTREE *t;
  345.     PAGE *h, **lp, **rp;
  346.     u_int *skip;
  347.     size_t ilen;
  348. {
  349.     PAGE *l, *r, *tp;
  350.     pgno_t npg;
  351.  
  352. #ifdef STATISTICS
  353.     ++bt_split;
  354. #endif
  355.     /* Put the new right page for the split into place. */
  356.     if ((r = __bt_new(t, &npg)) == NULL)
  357.         return (NULL);
  358.     r->pgno = npg;
  359.     r->lower = BTDATAOFF;
  360.     r->upper = t->bt_psize;
  361.     r->nextpg = h->nextpg;
  362.     r->prevpg = h->pgno;
  363.     r->flags = h->flags & P_TYPE;
  364.  
  365.     /*
  366.      * If we're splitting the last page on a level because we're appending
  367.      * a key to it (skip is NEXTINDEX()), it's likely that the data is
  368.      * sorted.  Adding an empty page on the side of the level is less work
  369.      * and can push the fill factor much higher than normal.  If we're
  370.      * wrong it's no big deal, we'll just do the split the right way next
  371.      * time.  It may look like it's equally easy to do a similar hack for
  372.      * reverse sorted data, that is, split the tree left, but it's not.
  373.      * Don't even try.
  374.      */
  375.     if (h->nextpg == P_INVALID && *skip == NEXTINDEX(h)) {
  376. #ifdef STATISTICS
  377.         ++bt_sortsplit;
  378. #endif
  379.         h->nextpg = r->pgno;
  380.         r->lower = BTDATAOFF + sizeof(indx_t);
  381.         *skip = 0;
  382.         *lp = h;
  383.         *rp = r;
  384.         return (r);
  385.     }
  386.  
  387.     /* Put the new left page for the split into place. */
  388.     if ((l = malloc(t->bt_psize)) == NULL) {
  389.         mpool_put(t->bt_mp, r, 0);
  390.         return (NULL);
  391.     }
  392.     l->pgno = h->pgno;
  393.     l->nextpg = r->pgno;
  394.     l->prevpg = h->prevpg;
  395.     l->lower = BTDATAOFF;
  396.     l->upper = t->bt_psize;
  397.     l->flags = h->flags & P_TYPE;
  398.  
  399.     /* Fix up the previous pointer of the page after the split page. */
  400.     if (h->nextpg != P_INVALID) {
  401.         if ((tp = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) {
  402.             free(l);
  403.             /* XXX mpool_free(t->bt_mp, r->pgno); */
  404.             return (NULL);
  405.         }
  406.         tp->prevpg = r->pgno;
  407.         mpool_put(t->bt_mp, tp, 0);
  408.     }
  409.  
  410.     /*
  411.      * Split right.  The key/data pairs aren't sorted in the btree page so
  412.      * it's simpler to copy the data from the split page onto two new pages
  413.      * instead of copying half the data to the right page and compacting
  414.      * the left page in place.  Since the left page can't change, we have
  415.      * to swap the original and the allocated left page after the split.
  416.      */
  417.     tp = bt_psplit(t, h, l, r, skip, ilen);
  418.  
  419.     /* Move the new left page onto the old left page. */
  420.     memmove(h, l, t->bt_psize);
  421.     if (tp == l)
  422.         tp = h;
  423.     free(l);
  424.  
  425.     *lp = h;
  426.     *rp = r;
  427.     return (tp);
  428. }
  429.  
  430. /*
  431.  * BT_ROOT -- Split the root page of a btree.
  432.  *
  433.  * Parameters:
  434.  *    t:    tree
  435.  *    h:    root page
  436.  *    lp:    pointer to left page pointer
  437.  *    rp:    pointer to right page pointer
  438.  *    skip:    pointer to index to leave open
  439.  *    ilen:    insert length
  440.  *
  441.  * Returns:
  442.  *    Pointer to page in which to insert or NULL on error.
  443.  */
  444. static PAGE *
  445. bt_root(t, h, lp, rp, skip, ilen)
  446.     BTREE *t;
  447.     PAGE *h, **lp, **rp;
  448.     u_int *skip;
  449.     size_t ilen;
  450. {
  451.     PAGE *l, *r, *tp;
  452.     pgno_t lnpg, rnpg;
  453.  
  454. #ifdef STATISTICS
  455.     ++bt_split;
  456.     ++bt_rootsplit;
  457. #endif
  458.     /* Put the new left and right pages for the split into place. */
  459.     if ((l = __bt_new(t, &lnpg)) == NULL ||
  460.         (r = __bt_new(t, &rnpg)) == NULL)
  461.         return (NULL);
  462.     l->pgno = lnpg;
  463.     r->pgno = rnpg;
  464.     l->nextpg = r->pgno;
  465.     r->prevpg = l->pgno;
  466.     l->prevpg = r->nextpg = P_INVALID;
  467.     l->lower = r->lower = BTDATAOFF;
  468.     l->upper = r->upper = t->bt_psize;
  469.     l->flags = r->flags = h->flags & P_TYPE;
  470.  
  471.     /* Split the root page. */
  472.     tp = bt_psplit(t, h, l, r, skip, ilen);
  473.  
  474.     *lp = l;
  475.     *rp = r;
  476.     return (tp);
  477. }
  478.  
  479. /*
  480.  * BT_RROOT -- Fix up the recno root page after it has been split.
  481.  *
  482.  * Parameters:
  483.  *    t:    tree
  484.  *    h:    root page
  485.  *    l:    left page
  486.  *    r:    right page
  487.  *
  488.  * Returns:
  489.  *    RET_ERROR, RET_SUCCESS
  490.  */
  491. static int
  492. bt_rroot(t, h, l, r)
  493.     BTREE *t;
  494.     PAGE *h, *l, *r;
  495. {
  496.     char *dest;
  497.  
  498.     /* Insert the left and right keys, set the header information. */
  499.     h->linp[0] = h->upper = t->bt_psize - NRINTERNAL;
  500.     dest = (char *)h + h->upper;
  501.     WR_RINTERNAL(dest,
  502.         l->flags & P_RLEAF ? NEXTINDEX(l) : rec_total(l), l->pgno);
  503.  
  504.     h->linp[1] = h->upper -= NRINTERNAL;
  505.     dest = (char *)h + h->upper;
  506.     WR_RINTERNAL(dest,
  507.         r->flags & P_RLEAF ? NEXTINDEX(r) : rec_total(r), r->pgno);
  508.  
  509.     h->lower = BTDATAOFF + 2 * sizeof(indx_t);
  510.  
  511.     /* Unpin the root page, set to recno internal page. */
  512.     h->flags &= ~P_TYPE;
  513.     h->flags |= P_RINTERNAL;
  514.     mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  515.  
  516.     return (RET_SUCCESS);
  517. }
  518.  
  519. /*
  520.  * BT_BROOT -- Fix up the btree root page after it has been split.
  521.  *
  522.  * Parameters:
  523.  *    t:    tree
  524.  *    h:    root page
  525.  *    l:    left page
  526.  *    r:    right page
  527.  *
  528.  * Returns:
  529.  *    RET_ERROR, RET_SUCCESS
  530.  */
  531. static int
  532. bt_broot(t, h, l, r)
  533.     BTREE *t;
  534.     PAGE *h, *l, *r;
  535. {
  536.     BINTERNAL *bi;
  537.     BLEAF *bl;
  538.     size_t nbytes;
  539.     char *dest;
  540.  
  541.     /*
  542.      * If the root page was a leaf page, change it into an internal page.
  543.      * We copy the key we split on (but not the key's data, in the case of
  544.      * a leaf page) to the new root page.
  545.      *
  546.      * The btree comparison code guarantees that the left-most key on any
  547.      * level of the tree is never used, so it doesn't need to be filled in.
  548.      */
  549.     nbytes = NBINTERNAL(0);
  550.     h->linp[0] = h->upper = t->bt_psize - nbytes;
  551.     dest = (char *)h + h->upper;
  552.     WR_BINTERNAL(dest, 0, l->pgno, 0);
  553.  
  554.     switch(h->flags & P_TYPE) {
  555.     case P_BLEAF:
  556.         bl = GETBLEAF(r, 0);
  557.         nbytes = NBINTERNAL(bl->ksize);
  558.         h->linp[1] = h->upper -= nbytes;
  559.         dest = (char *)h + h->upper;
  560.         WR_BINTERNAL(dest, bl->ksize, r->pgno, 0);
  561.         memmove(dest, bl->bytes, bl->ksize);
  562.  
  563.         /*
  564.          * If the key is on an overflow page, mark the overflow chain
  565.          * so it isn't deleted when the leaf copy of the key is deleted.
  566.          */
  567.         if (bl->flags & P_BIGKEY &&
  568.             bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR)
  569.             return (RET_ERROR);
  570.         break;
  571.     case P_BINTERNAL:
  572.         bi = GETBINTERNAL(r, 0);
  573.         nbytes = NBINTERNAL(bi->ksize);
  574.         h->linp[1] = h->upper -= nbytes;
  575.         dest = (char *)h + h->upper;
  576.         memmove(dest, bi, nbytes);
  577.         ((BINTERNAL *)dest)->pgno = r->pgno;
  578.         break;
  579.     default:
  580.         abort();
  581.     }
  582.  
  583.     /* There are two keys on the page. */
  584.     h->lower = BTDATAOFF + 2 * sizeof(indx_t);
  585.  
  586.     /* Unpin the root page, set to btree internal page. */
  587.     h->flags &= ~P_TYPE;
  588.     h->flags |= P_BINTERNAL;
  589.     mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  590.  
  591.     return (RET_SUCCESS);
  592. }
  593.  
  594. /*
  595.  * BT_PSPLIT -- Do the real work of splitting the page.
  596.  *
  597.  * Parameters:
  598.  *    t:    tree
  599.  *    h:    page to be split
  600.  *    l:    page to put lower half of data
  601.  *    r:    page to put upper half of data
  602.  *    pskip:    pointer to index to leave open
  603.  *    ilen:    insert length
  604.  *
  605.  * Returns:
  606.  *    Pointer to page in which to insert.
  607.  */
  608. static PAGE *
  609. bt_psplit(t, h, l, r, pskip, ilen)
  610.     BTREE *t;
  611.     PAGE *h, *l, *r;
  612.     u_int *pskip;
  613.     size_t ilen;
  614. {
  615.     BINTERNAL *bi;
  616.     BLEAF *bl;
  617.     RLEAF *rl;
  618.     EPGNO *c;
  619.     PAGE *rval;
  620.     void *src;
  621.     indx_t full, half, nxt, off, skip, top, used;
  622.     size_t nbytes;
  623.     int bigkeycnt, isbigkey;
  624.  
  625.     /*
  626.      * Split the data to the left and right pages.  Leave the skip index
  627.      * open.  Additionally, make some effort not to split on an overflow
  628.      * key.  This makes internal page processing faster and can save
  629.      * space as overflow keys used by internal pages are never deleted.
  630.      */
  631.     bigkeycnt = 0;
  632.     skip = *pskip;
  633.     full = t->bt_psize - BTDATAOFF;
  634.     half = full / 2;
  635.     used = 0;
  636.     for (nxt = off = 0, top = NEXTINDEX(h); nxt < top; ++off) {
  637.         if (skip == off) {
  638.             nbytes = ilen;
  639.             isbigkey = 0;        /* XXX: not really known. */
  640.         } else
  641.             switch (h->flags & P_TYPE) {
  642.             case P_BINTERNAL:
  643.                 src = bi = GETBINTERNAL(h, nxt);
  644.                 nbytes = NBINTERNAL(bi->ksize);
  645.                 isbigkey = bi->flags & P_BIGKEY;
  646.                 break;
  647.             case P_BLEAF:
  648.                 src = bl = GETBLEAF(h, nxt);
  649.                 nbytes = NBLEAF(bl);
  650.                 isbigkey = bl->flags & P_BIGKEY;
  651.                 break;
  652.             case P_RINTERNAL:
  653.                 src = GETRINTERNAL(h, nxt);
  654.                 nbytes = NRINTERNAL;
  655.                 isbigkey = 0;
  656.                 break;
  657.             case P_RLEAF:
  658.                 src = rl = GETRLEAF(h, nxt);
  659.                 nbytes = NRLEAF(rl);
  660.                 isbigkey = 0;
  661.                 break;
  662.             default:
  663.                 abort();
  664.             }
  665.  
  666.         /*
  667.          * If the key/data pairs are substantial fractions of the max
  668.          * possible size for the page, it's possible to get situations
  669.          * where we decide to try and copy too much onto the left page.
  670.          * Make sure that doesn't happen.
  671.          */
  672.         if (skip <= off && used + nbytes >= full) {
  673.             --off;
  674.             break;
  675.         }
  676.  
  677.         /* Copy the key/data pair, if not the skipped index. */
  678.         if (skip != off) {
  679.             ++nxt;
  680.  
  681.             l->linp[off] = l->upper -= nbytes;
  682.             memmove((char *)l + l->upper, src, nbytes);
  683.         }
  684.  
  685.         used += nbytes;
  686.         if (used >= half) {
  687.             if (!isbigkey || bigkeycnt == 3)
  688.                 break;
  689.             else
  690.                 ++bigkeycnt;
  691.         }
  692.     }
  693.  
  694.     /*
  695.      * Off is the last offset that's valid for the left page.
  696.      * Nxt is the first offset to be placed on the right page.
  697.      */
  698.     l->lower += (off + 1) * sizeof(indx_t);
  699.  
  700.     /*
  701.      * If splitting the page that the cursor was on, the cursor has to be
  702.      * adjusted to point to the same record as before the split.  If the
  703.      * cursor is at or past the skipped slot, the cursor is incremented by
  704.      * one.  If the cursor is on the right page, it is decremented by the
  705.      * number of records split to the left page.
  706.      *
  707.      * Don't bother checking for the B_SEQINIT flag, the page number will
  708.      * be P_INVALID.
  709.      */
  710.     c = &t->bt_bcursor;
  711.     if (c->pgno == h->pgno) {
  712.         if (c->index >= skip)
  713.             ++c->index;
  714.         if (c->index < nxt)            /* Left page. */
  715.             c->pgno = l->pgno;
  716.         else {                    /* Right page. */
  717.             c->pgno = r->pgno;
  718.             c->index -= nxt;
  719.         }
  720.     }
  721.  
  722.     /*
  723.      * If the skipped index was on the left page, just return that page.
  724.      * Otherwise, adjust the skip index to reflect the new position on
  725.      * the right page.
  726.      */
  727.     if (skip <= off) {
  728.         skip = 0;
  729.         rval = l;
  730.     } else {
  731.         rval = r;
  732.         *pskip -= nxt;
  733.     }
  734.  
  735.     for (off = 0; nxt < top; ++off) {
  736.         if (skip == nxt) {
  737.             ++off;
  738.             skip = 0;
  739.         }
  740.         switch (h->flags & P_TYPE) {
  741.         case P_BINTERNAL:
  742.             src = bi = GETBINTERNAL(h, nxt);
  743.             nbytes = NBINTERNAL(bi->ksize);
  744.             break;
  745.         case P_BLEAF:
  746.             src = bl = GETBLEAF(h, nxt);
  747.             nbytes = NBLEAF(bl);
  748.             break;
  749.         case P_RINTERNAL:
  750.             src = GETRINTERNAL(h, nxt);
  751.             nbytes = NRINTERNAL;
  752.             break;
  753.         case P_RLEAF:
  754.             src = rl = GETRLEAF(h, nxt);
  755.             nbytes = NRLEAF(rl);
  756.             break;
  757.         default:
  758.             abort();
  759.         }
  760.         ++nxt;
  761.         r->linp[off] = r->upper -= nbytes;
  762.         memmove((char *)r + r->upper, src, nbytes);
  763.     }
  764.     r->lower += off * sizeof(indx_t);
  765.  
  766.     /* If the key is being appended to the page, adjust the index. */
  767.     if (skip == top)
  768.         r->lower += sizeof(indx_t);
  769.  
  770.     return (rval);
  771. }
  772.  
  773. /*
  774.  * BT_PRESERVE -- Mark a chain of pages as used by an internal node.
  775.  *
  776.  * Chains of indirect blocks pointed to by leaf nodes get reclaimed when the
  777.  * record that references them gets deleted.  Chains pointed to by internal
  778.  * pages never get deleted.  This routine marks a chain as pointed to by an
  779.  * internal page.
  780.  *
  781.  * Parameters:
  782.  *    t:    tree
  783.  *    pg:    page number of first page in the chain.
  784.  *
  785.  * Returns:
  786.  *    RET_SUCCESS, RET_ERROR.
  787.  */
  788. static int
  789. bt_preserve(t, pg)
  790.     BTREE *t;
  791.     pgno_t pg;
  792. {
  793.     PAGE *h;
  794.  
  795.     if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  796.         return (RET_ERROR);
  797.     h->flags |= P_PRESERVE;
  798.     mpool_put(t->bt_mp, h, MPOOL_DIRTY);
  799.     return (RET_SUCCESS);
  800. }
  801.  
  802. /*
  803.  * REC_TOTAL -- Return the number of recno entries below a page.
  804.  *
  805.  * Parameters:
  806.  *    h:    page
  807.  *
  808.  * Returns:
  809.  *    The number of recno entries below a page.
  810.  *
  811.  * XXX
  812.  * These values could be set by the bt_psplit routine.  The problem is that the
  813.  * entry has to be popped off of the stack etc. or the values have to be passed
  814.  * all the way back to bt_split/bt_rroot and it's not very clean.
  815.  */
  816. static recno_t
  817. rec_total(h)
  818.     PAGE *h;
  819. {
  820.     recno_t recs;
  821.     indx_t nxt, top;
  822.  
  823.     for (recs = 0, nxt = 0, top = NEXTINDEX(h); nxt < top; ++nxt)
  824.         recs += GETRINTERNAL(h, nxt)->nrecs;
  825.     return (recs);
  826. }
  827.